In recent years, consumers have been provided with a variety of devices and systems to enable them to locate places on a digital map. The term “place” is a general term used throughout the description of embodiments of this invention. The term “place” includes street addresses, buildings located at street addresses such as businesses and landmarks, and facilities located at a number of street addresses such as shopping malls and business parks. The variety of devices and systems used by consumers are in the form of in-vehicle navigation systems that enable drivers to navigate over streets and roads; hand-held devices such as personal digital assistants (“PDAs”), personal navigation devices (PNDs), and cell phones or other types of mobile devices that can do the same; desktop applications, and Internet applications in which users can generate maps showing desired places. The common aspect in all of these and other types of devices and systems is a map database of geographic features, vectors and attributes, and software to access, manipulate and navigate the map database in response to user inputs.
Essentially, in all of these devices and systems a user can enter a desired place and the returned result will be the location of that place. Typically, users will enter the name of a business, such as a restaurant for example, or a destination landmark, such as the Golden Gate Bridge for example, or a street address, etc. The device/system then determines and returns the location of the requested place. The location may be shown on a map display, or may be used to calculate and display driving directions to the location in a known manner, or used in other ways.
Map databases provide information about locations of houses and buildings on streets. Map database developers include address data over a given address range for a given street or street segment (address segment) in map databases. The address range will include a group of building or house numbers corresponding to a given side of the street segment, with starting house numbers and positions, ending house numbers and positions, and optionally some intermediate house numbers and positions.
To locate a desired place in response to a user input or selection of a desired destination, the software of the device or system first determined the street address of the place, then located the street segment that has an address range containing the desired selected or input address, and then performed interpolation within the address range to estimate the location of the place. However, the interpolation algorithm would often have trouble accounting for variations in the real world distribution of buildings or house numbers along a given street block. For example, there may have been a park at the beginning or in the middle of the block, houses may have been distributed along the block non-uniformly, and/or buildings at the ends of address ranges may not have been located exactly at street intersections.
Ideally, building and/or house numbers at the end of an address range will represent real building addresses, thus reducing error in interpolating intermediate house numbers. However, this is not always the case. Some map databases are modeled with address ranges using potential building or house numbers at the end points, and this exacerbates the problem of accurately interpolating intermediate building or house numbers. For example, a map database may model address ranges using potential building or house numbers as assigned by the U.S. Postal Service. Further, as an example, in downtown New York City, where streets are broken up into blocks of 100 address numbers, building or house numbers along a block side seldom represent the entire address range and often fall short of completing the range at one end or the other.
Interpolation using the above methods may have errors of fifty percent or more of the length of the stored street segments or ranges. These interpolation errors can translate into tens or hundreds of meters of errors, for example, possibly making a desired place out of a user's range of sight for a user who has navigated to the interpolated location of the desired destination.
Known digital map databases, as shown in FIG. 1, include address segments or address segment sides commonly represented as address segment vectors in the known digital map databases. Such address segments or address segment sides, commonly represented as address segment vectors, are typically stored, in memories containing the map databases, as features with start and end points, connected by a line (possibly shaped as shown in FIG. 1 for example using shape points SP which will be discussed hereafter). Such address segment vectors typically represent one side of the address segment, an address segment side (wherein address segment is understood to mean any travel route including but not limited to roads, streets, highways, etc., identifiable by name and including known addresses).
As an example, a start point such as #2 of FIG. 1 and an end point such as #98 of FIG. 1 typically represent starting and ending house or building numbers of an address segment or side of a street. An address range is used to represent all of the addresses for an address segment or address segment side and typically runs from the starting house number to the ending house number (for example #2 to #98 in FIG. 1), possibly with some parity (only including even numbers for one side of the address segment and only including odd numbers for the other side of the address segment, or including both if both sides of an address segment are represented).
An address range for an address segment or address segment side is typically stored with the address segment vector in the digital map database and can be used, in a known manner, in navigation and other types of map techniques for locating position or travel destinations in a known manner. Typically, address segment vectors are stored in the digital map database along with attribute information including but not limited to, for example, speed limits on the address segment, any indication of turn restrictions or one way only access, census codes, zip codes, street names, etc.
Typically, the locations of intermediate house numbers (between the start and end points of the address range) are calculated using linear interpolation within the address range in a known manner. As shown in FIG. 2 for example, house #50 will typically be determined by a linear interpolation to be midway along the shape of the address segment of FIG. 2, between address #2 and address #98. Such interpolation is commonly used in geocoding and navigation applications which utilize digital map databases to determine locations, travel destinations, places, etc.
There are several problems with use of linear interpolation methodology that can lead to interpolation error. First, some digital map databases do not use real building numbers for the start and end points of an address segment. Instead, they use postal potential addresses (the addresses reserved for that address segment by the U.S. Postal Service) in order to accommodate locating buildings that may be constructed after the digital map database is built or for ease of postal delivery. For example, in the potential postal range on a segment is #2 to #98 as shown in FIGS. 1 and 2 for example, linear interpolation following the curvature of the road will locate address #50 near the midpoint of the segment. However, if the actual end point addresses are #2 and #60 as shown in FIG. 3 for example, instead of correctly interpolating the address at point #50b in FIG. 3, linear interpolation will be used using the postal potential address range of #2 to #98 and will locate the address at point #50a as shown in FIG. 3, following the curvature of the segment. Thus, an error will occur in the navigation and/or geocoding applications.
Further, as shown in FIG. 4, in reality addresses are not typically distributed linearly on a segment. FIG. 4 shows an example photo including a large park or vacant lot 140 in the middle of the block, which may cause address numbers to be unevenly distributed along an address segment.
Some digital map databases have been constructed using actual address numbers as start and end points of segments, instead of postal potentials. While this may improve on interpolation of intermediate points, linear interpolation can still show large errors when addresses are not distributed uniformly along a segment, for example, when there is a park, parking lot, or apartment building on the block. In addition, non-linear interpolation methods could be used, such as logarithmic interpolations which assume that physical addresses are concentrated at one end of address segments. However, this method also fails when addresses are not readily distributed according to the algorithm used for intermediate point interpolation.
Still other digital map databases have been constructed with some or all individual (point) addresses added to the address segments according to their actual location. An example of this is discussed in U.S. patent application Ser. No. 11/351,156 filed on Feb. 8, 2006, entitled “MAP DATABASE HAVING ADDRESS POINTS FOR DETERMINING DESTINATIONS” to Michael Geilich, the entire contents of which are hereby incorporated herein by reference. While this provides sufficient information to either directly find the address point you are looking for, or at least allows for the shortest interpolation so that the error is smallest, it also represents a considerable change in the algorithms used to determine the location from the address and potentially expensive storage in the device for the address point data. Such new and different logic would require significant software updates to the device using this new improved map. In older units it may be difficult, expensive or even impossible to introduce such software change.